import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 501. 二叉搜索树中的众数
 * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
 */
public class Solutions_501 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1);
//        root.right = new TreeNode(2);
//        root.right.left = new TreeNode(2);  // output: {2}

        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);  // output: {1, 2}

        int[] result = findMode(root);
        System.out.println(Arrays.toString(result));
    }

    // 递归
    public static int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        findMode(root, list);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private static int maxCount = 0;  // 最大的出现次数
    private static int curCount = 0;  // 当前遍历元素到目前为止出现的次数
    private static TreeNode preNode = null;  // 前一节点

    // 根据二叉搜索树的特性，根节点一定大于等于左子节点，小于等于右子节点
    public static void findMode(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        findMode(root.left, list);
        // 记录出现次数
        if (preNode != null && root.val == preNode.val) {
            curCount ++;
        } else {
            curCount = 1;
        }
        if (curCount >= maxCount) {
            if (curCount > maxCount) {
                // 出现最大的出现次数
                maxCount = curCount;
                list.clear();
            }
            // 出现次数相等时，加入到列表中
            list.add(root.val);
        }
        // 遍历右子节点前，将根节点设置为前一节点
        preNode = root;
        findMode(root.right, list);
    }
}
